#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

class Solution
{
public:
    int getMidR(int begin, int end, int r, int c)
    {
        return ((begin + end) / 2) / c;
    }

    int getMidC(int begin, int end, int r, int c)
    {
        return ((begin + end) / 2) % c;
    }

    bool contain(vector<vector<int>> &matrix, int target, int total, int r, int c)
    {
        int begin = 0, end = total - 1;
        int midR, midC;
        while (begin <= end)
        {
            midR = getMidR(begin, end, r, c);
            midC = getMidC(begin, end, r, c);
            if (matrix[midR][midC] > target)
            {
                end = (midR * c + midC) - 1;
            }
            else if (matrix[midR][midC] < target)
            {
                begin = (midR * c + midC) + 1;
            }
            else
            {
                return true;
            }
        }
        return false;
    }

    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int r = matrix.size(), c = matrix[0].size();
        int total = r * c;
        return contain(matrix, target, total, r, c);
    }
};

void test1()
{
    Solution sol;
    vector<vector<int>> matrix{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
    /* for(auto vec: matrix){
        for(auto i: vec){
            cout << i << " ";
        }
        cout << endl;
    } */

    cout << sol.searchMatrix(matrix, 2) << endl;
    
}

int main(int argc, char const *argv[])
{
    test1();
    return 0;
}
